home *** CD-ROM | disk | FTP | other *** search
/ PCGUIA 127 / PC Guia 127.iso / Software / Produtividade / OpenOffice.org 2.0.1 / openofficeorg4.cab / sortperf.py < prev    next >
Text File  |  2005-11-19  |  5KB  |  170 lines
  1. """Sort performance test.
  2.  
  3. See main() for command line syntax.
  4. See tabulate() for output format.
  5.  
  6. """
  7.  
  8. import sys
  9. import time
  10. import random
  11. import marshal
  12. import tempfile
  13. import os
  14.  
  15. td = tempfile.gettempdir()
  16.  
  17. def randfloats(n):
  18.     """Return a list of n random floats in [0, 1)."""
  19.     # Generating floats is expensive, so this writes them out to a file in
  20.     # a temp directory.  If the file already exists, it just reads them
  21.     # back in and shuffles them a bit.
  22.     fn = os.path.join(td, "rr%06d" % n)
  23.     try:
  24.         fp = open(fn, "rb")
  25.     except IOError:
  26.         r = random.random
  27.         result = [r() for i in xrange(n)]
  28.         try:
  29.             try:
  30.                 fp = open(fn, "wb")
  31.                 marshal.dump(result, fp)
  32.                 fp.close()
  33.                 fp = None
  34.             finally:
  35.                 if fp:
  36.                     try:
  37.                         os.unlink(fn)
  38.                     except os.error:
  39.                         pass
  40.         except IOError, msg:
  41.             print "can't write", fn, ":", msg
  42.     else:
  43.         result = marshal.load(fp)
  44.         fp.close()
  45.         # Shuffle it a bit...
  46.         for i in range(10):
  47.             i = random.randrange(n)
  48.             temp = result[:i]
  49.             del result[:i]
  50.             temp.reverse()
  51.             result.extend(temp)
  52.             del temp
  53.     assert len(result) == n
  54.     return result
  55.  
  56. def flush():
  57.     sys.stdout.flush()
  58.  
  59. def doit(L):
  60.     t0 = time.clock()
  61.     L.sort()
  62.     t1 = time.clock()
  63.     print "%6.2f" % (t1-t0),
  64.     flush()
  65.  
  66. def tabulate(r):
  67.     """Tabulate sort speed for lists of various sizes.
  68.  
  69.     The sizes are 2**i for i in r (the argument, a list).
  70.  
  71.     The output displays i, 2**i, and the time to sort arrays of 2**i
  72.     floating point numbers with the following properties:
  73.  
  74.     *sort: random data
  75.     \sort: descending data
  76.     /sort: ascending data
  77.     3sort: ascending, then 3 random exchanges
  78.     +sort: ascending, then 10 random at the end
  79.     %sort: ascending, then randomly replace 1% of the elements w/ random values
  80.     ~sort: many duplicates
  81.     =sort: all equal
  82.     !sort: worst case scenario
  83.  
  84.     """
  85.     cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"])
  86.     fmt = ("%2s %7s" + " %6s"*len(cases))
  87.     print fmt % (("i", "2**i") + cases)
  88.     for i in r:
  89.         n = 1 << i
  90.         L = randfloats(n)
  91.         print "%2d %7d" % (i, n),
  92.         flush()
  93.         doit(L) # *sort
  94.         L.reverse()
  95.         doit(L) # \sort
  96.         doit(L) # /sort
  97.  
  98.         # Do 3 random exchanges.
  99.         for dummy in range(3):
  100.             i1 = random.randrange(n)
  101.             i2 = random.randrange(n)
  102.             L[i1], L[i2] = L[i2], L[i1]
  103.         doit(L) # 3sort
  104.  
  105.         # Replace the last 10 with random floats.
  106.         if n >= 10:
  107.             L[-10:] = [random.random() for dummy in range(10)]
  108.         doit(L) # +sort
  109.  
  110.         # Replace 1% of the elements at random.
  111.         for dummy in xrange(n // 100):
  112.             L[random.randrange(n)] = random.random()
  113.         doit(L) # %sort
  114.  
  115.         # Arrange for lots of duplicates.
  116.         if n > 4:
  117.             del L[4:]
  118.             L = L * (n // 4)
  119.             # Force the elements to be distinct objects, else timings can be
  120.             # artificially low.
  121.             L = map(lambda x: --x, L)
  122.         doit(L) # ~sort
  123.         del L
  124.  
  125.         # All equal.  Again, force the elements to be distinct objects.
  126.         L = map(abs, [-0.5] * n)
  127.         doit(L) # =sort
  128.         del L
  129.  
  130.         # This one looks like [3, 2, 1, 0, 0, 1, 2, 3].  It was a bad case
  131.         # for an older implementation of quicksort, which used the median
  132.         # of the first, last and middle elements as the pivot.
  133.         half = n // 2
  134.         L = range(half - 1, -1, -1)
  135.         L.extend(range(half))
  136.         # Force to float, so that the timings are comparable.  This is
  137.         # significantly faster if we leave tham as ints.
  138.         L = map(float, L)
  139.         doit(L) # !sort
  140.         print
  141.  
  142. def main():
  143.     """Main program when invoked as a script.
  144.  
  145.     One argument: tabulate a single row.
  146.     Two arguments: tabulate a range (inclusive).
  147.     Extra arguments are used to seed the random generator.
  148.  
  149.     """
  150.     # default range (inclusive)
  151.     k1 = 15
  152.     k2 = 20
  153.     if sys.argv[1:]:
  154.         # one argument: single point
  155.         k1 = k2 = int(sys.argv[1])
  156.         if sys.argv[2:]:
  157.             # two arguments: specify range
  158.             k2 = int(sys.argv[2])
  159.             if sys.argv[3:]:
  160.                 # derive random seed from remaining arguments
  161.                 x = 1
  162.                 for a in sys.argv[3:]:
  163.                     x = 69069 * x + hash(a)
  164.                 random.seed(x)
  165.     r = range(k1, k2+1)                 # include the end point
  166.     tabulate(r)
  167.  
  168. if __name__ == '__main__':
  169.     main()
  170.